#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
constexpr int MAXN = 100, INF = 1 << 30;
int d[MAXN];
struct edge {int from, to, cost;};
edge es[MAXN]; // 这个相当于保存所有的边信息
int V, E; // V表示节点数, E表示边的数目


// 计算s节点到其余节点的最短路径, 比我自己的思路要好很多
/**
 * 我当时想的是首先选取一个最小的节点, 然后这个节点所有的边, 连过去的最小距离作为下个开始的迭代的点
 * 但是这样一来的话需要维护已经迭代过的点, 其次有的点可能没有可达的边, 这种思想比较偏向于迪杰斯特拉算法
 * 
 * 书上的思路好: 它的目的就是迭代每一条边, 迭代的过程不断计算一个边的最小值, 最后看是否更新, 如果不再更新了, 那么就表示迭代结束了
 * 只要不存在负权值, 那么久不会会有迭代终止的时候
 */ 
void shortest_path(int s) {
    for (int i = 0; i < V; i++) d[i] = INF;
    d[s] = 0;
    int start = s;
    while (true) {
        bool update = false;
        for (int i = 0; i < E; i++) {
            edge e = es[i];
            if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
        if (!update) break;
    }
}

// 如果存在了负圈, 那么就会迭代V次

bool find_negative_loop() {
    memset(d, 0, sizeof(d));
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < E; j++) {
            edge e = es[j];
            if (d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
                // 如果第V次仍然存在更新, 那么就表示存在负圈
                if (i == V - 1) return true;
            }
        }
    }
    return false;
}